1. Field of the Invention
The present invention generally relates to a route setting method and a route setting apparatus in a navigation system, and more particularly to a route setting method and a route setting apparatus used in a car navigation system for performing a route self-guidance of a vehicle to a destination. 2. Description of the Related Art
There is a so-called "built-in type navigation apparatus" as a measuring apparatus for various movable bodies such as a vehicle, an airplane, a ship etc. This built-in type navigation apparatus is constructed to obtain two dimensional displacement (i.e. a vector amount) of the movable body from an azimuth data of an azimuth sensor and speed data of a speed sensor and obtain a present position by integrating this two dimensional displacement on a standard point. Namely, in case of an automobile for example, it is constructed such that the number of pulses which are generated during one rotation of a drive shaft is set in advance, and that the travel distance is obtained by multiplying a distance, which is calculated from the total number of the pulses generated from the standard point to the present position, by a distance correction coefficient.
There is also a GPS (Global Positioning System) type navigation apparatus as a measuring apparatus, which utilizes artificial satellites. This GPS type navigation apparatus is constructed as follows. Namely, it receives electric waves of three or more GPS satellites normally, and calculates a present position of a receiving point from the pseudo-distance data, which include a time offset of a receiver between each GPS satellite and the receiving point and the positional data of each GPS satellite. Then, an information processing device reads out map data, which include the calculated present position, from a map data storing device, to take in the data. Then, the information processing device forms image data from the taken-in map data and the information of the present position, and sends it to the display device to perform the image display. By this image, the automobile driver etc. who is a user can recognize the present position in relation with the map.
The above described navigation apparatus may perform not only a display of a vehicle in the above described manner but also an automatic route setting operation by inputting a starting position and a destination, so as to guide a vehicle to the destination on the basis of the automatically set shortest route.
In such an automatic route setting operation, as a method for automatically performing the route setting operation, there is the Dijkstra method.
The Dijkstra method determines the shortest route by determining a node, which corresponds to a route position such as a crossing to be routed, one after another from the small peripheral area around the starting position (starting node), and gradually expands the area for determining the node to finish the process at the time when the shortest route to the destination (objective node) is finally obtained.
The algorithm of the Dijkstra method is as following.
Namely, all of the nodes which are connected to the starting node via links are set as candidacy nodes. Then, the node with the minimum cost (link length is the minimum) is set as a confirmed node. Then, all of the nodes which are connected to the confirmed node via links are set as new candidacy nodes. However, in the event that there is a node which has already been a candidacy node, if the cost to the confirmed node is small, the route passing through the confirmed node is adopted as the shortest route. Finally, the above processes of setting the node and adopting the route are repeated, and when the objective node coincides with the confirmed node, the process is ended.
By this algorithm, the shortest route from the starting position to the destination can be automatically obtained according to the Dijkstra method.
However, according to the study and analysis conducted by the inventors of the present application, this route setting method in the navigation system by means of the Dijkstra method has a serious drawback as explained hereinbelow with referring to FIG. 3 and FIG. 5.
FIG. 3 is a route diagram for explaining a concrete operation of the route setting system.
In FIG. 3, it is assumed that the starting position is node A and the destination is node G, the route of node D .fwdarw. node F .fwdarw. node G cannot be adopted since the right turn is prohibited thereon, and the U turn is also prohibited. Each numeral represents a link length i.e. a distance between nodes.
FIG. 5 is a diagram for explaining a concrete operation of the route setting system.
In FIG. 5, in the expression X (Y, Z), X represents the candidacy node name, Y represents the previous node name before arriving at the candidacy node X by one node, and Z represents the integrated cost (integrated distance) up to the candidacy node X.
Firstly, the candidacy nodes obtained as for the node A which is the starting position are nodes B and C. Since the node which has the minimum cost among these candidacy nodes is the node B, the node B is adopted as the confirmed node.
As a result, the node D which is connected to the node B is adopted as the new candidacy node, and the candidacy nodes become the nodes C and D. Since, among these candidacy nodes, the node which has the minimum cost is the node C, the node C is adopted as the confirmed node.
Successively, the node E which is connected to the node C is adopted as the new candidacy node, and the candidacy nodes become the nodes D and E. Since, among these candidacy nodes, the node which has the minimum cost is the node D, the node D is adopted as the confirmed node.
Further, node F which is connected to node E is adopted as the new candidacy node, and the candidacy nodes become the nodes E and F. Since, among these candidacy nodes, the node which has the minimum cost is node F, node F is adopted as the confirmed node.
Here node E which is connected to node F has been already adopted as the candidacy node. Since the cost becomes smaller in case of reaching node E through node F, node E passing via node F is adopted as the new candidacy node. Node H which is connected to node F is also adopted as the candidacy node. On the other hand, node G is not adopted as the candidacy node since the right turn is prohibited on the route of node D .fwdarw. node F .fwdarw. node G.
Although each of the candidacy nodes E and H has the minimum cost, since, node E has been already adopted as the candidacy node in the previous step, node E is adopted as the confirmed node because the priority thereof is higher.
In the event that a plurality of nodes each having the minimum cost are adopted simultaneously as the candidacy nodes, the node with the smallest node number among these nodes is adopted as the confirmed node. For example, if they are node A and node C, node A is adopted as the confirmed node, and if they are node E and node D, node D is adopted as the confirmed node.
There remains only node H, which is adopted as the confirmed node.
In this manner, according to the study and analysis by the inventors of the present application, in the above explained route setting method by means of the Dijkstra method, there arises a case where the node G, i.e. the destination, cannot be reached if the traffic regulation etc. is considered, which is a serious problem in the navigation system in a practical sense.
In addition, according to the study and analysis by the present inventors of the present application, in the above explained Dijkstra method, in order to express the traffic regulation condition e.g. the right or left turn prohibition and the U turn prohibition, it becomes necessary to express it by use of a directional graph as shown in FIG. 6A. Thus, at the presence of a crossing street, since the directional graph is employed, the data amount required for the route setting operation is increased to be four times as high as the case where only the non-directional graph by use of data having no directional property (distance only) as shown in FIG. 6B is employed, which is another serious problem of the navigation system.